import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution407 {

    static final int[][] direct = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    class LocInfo{
        int x;
        int y;
        int height;

        public LocInfo(int x, int y, int height) {
            this.x = x;
            this.y = y;
            this.height = height;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        PriorityQueue<LocInfo> priorityQueue = new PriorityQueue<>(new Comparator<LocInfo>() {
            @Override
            public int compare(LocInfo o1, LocInfo o2) {
                return o1.height - o2.height;
            }
        });
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i == 0 || i == m-1 || j == 0 || j == n-1){
                    priorityQueue.offer(new LocInfo(j, i, heightMap[i][j]));
                    visited[i][j] = true;
                }
            }
        }
        for (; !priorityQueue.isEmpty(); ) {
            LocInfo tmpLoc = priorityQueue.poll();
            for (int i = 0; i < direct.length; i++) {
                int tmpX = tmpLoc.x + direct[i][0], tmpY = tmpLoc.y + direct[i][1];
                if(0 <= tmpX && tmpX < n && 0 <= tmpY && tmpY < m && !visited[tmpY][tmpX]){
                    int tmpHeight = heightMap[tmpY][tmpX];
                    if(tmpLoc.height > tmpHeight){
                        res += tmpLoc.height - tmpHeight;
                    }
                    visited[tmpY][tmpX] = true;
                    priorityQueue.offer(new LocInfo(tmpX, tmpY, Math.max(tmpLoc.height, tmpHeight)));
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution407 s = new Solution407();
        System.out.println(s.trapRainWater(new int[][]{{1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1}}));
    }
}
